/*
二分查找
进行二分查找的必须要先排好序
*/
#include<iostream>
#include <algorithm>
using namespace std;
int BinarySearch(int* arr,int target,int begin,int end){
	if(begin > end){
		return -1;
	}
	int mid = (begin + end)/2;
	if(arr[mid] == target){
		return mid;
	}
	else if(arr[mid] < target){
		return BinarySearch(arr,target,mid+1,end);		//这里要调用自己，用return！
	}
	else{
		return BinarySearch(arr,target,begin,mid-1);
	}
}
int BinarySearchIterative(int* arr,int target,int begin,int end){
	while( begin <= end){		//注意这里的 =
		int m = (begin+end)/2;
		if(arr[m] < target ){
			begin = m+1;		//从两边切割，不再到m，不然有可能造成死循环
		}
		else if(arr[m] > target){
			end = m-1;			//同理
		}
		else{
			return m;
		}
	}
	return -1;
}
void Print(int* arr,int len){
	for(int i = 0;i < len;i++){
		cout<<*(arr+i)<<"  ";
	}
	cout<<endl;
}
int main(int argc, char const *argv[])
{
	int arr[10] = {4,2,5,7,1,9,6,8,0,3};
	Print(arr,10);
	sort(arr,arr+10);
	Print(arr,10);
	cout<<BinarySearchIterative(arr,6,0,9)<<endl;
	return 0;
}